/*
** compress.c
**
** Pictor, Version 1.51, Copyright (c) 1992-94 SoftCircuits
** Redistributed by permission.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "compress.h"

#define DEBUG  1     /* 1 = enable internal, fatal errors */

#define TABLE_SIZE   0xFF  /* number of different possible characters */
#define MAX_BITS     50


/* static variable declarations */
static BYTE *buffer;
static WORD index;
static BYTE curr_bit;
static NODE *leaf_table[TABLE_SIZE];
static NODE *root_node;


/*
** Writes a bit to the buffer.
*/
static void write_bit(BYTE bit)
{
	if(curr_bit == 0) {
		index++;
		curr_bit = 1;
	}

	if(bit == 0) {
		buffer[index] &= ~curr_bit;
	}
	else {
		buffer[index] |= curr_bit;
	}
	curr_bit <<= 1;

} /* write_bit */

/*
** Writes a node to the buffer.
*/
static void write_node(NODE *node_ptr)
{
	static BYTE stack[MAX_BITS];
	NODE *last_node;
	WORD stack_ptr = 0;

	last_node = node_ptr;
	node_ptr = node_ptr->parent;
	for( ;last_node != root_node;node_ptr = node_ptr->parent) {

#if(DEBUG)

		/* caused by bad argument or corrupt code tree */
		if(node_ptr == NULL) {
			printf("Internal error : Module %s, Line %d\n",__FILE__,__LINE__);
			exit(-1);
		}
		/* required bits exceed MAX_BITS (should never happen) */
		if(stack_ptr >= MAX_BITS) {
			printf("Internal error : Module %s, Line %d\n",__FILE__,__LINE__);
			exit(-1);
		}

#endif

		stack[stack_ptr++] = (BYTE)(node_ptr->child1 == last_node);
		last_node = node_ptr;
	}

	while(stack_ptr > 0) {
		write_bit(stack[--stack_ptr]);
	}

} /* write_node */

/*
** Compresses an array. Returns length of compressed array.
*/
WORD compress(BYTE *in_array,WORD len,BYTE *out_array,NODE *root)
{
	WORD i;

	buffer = out_array;  /* set variables for write_bit() */
	index = 0;
	curr_bit = 1;

	root_node = root;

	for(i = 0;i < len;i++) {

#if(DEBUG)

		/* character found that was not included in compression code tree */
		if(leaf_table[in_array[i]] == NULL) {
			printf("Internal error : Module %s, Line %d\n",__FILE__,__LINE__);
			exit(-1);
		}

#endif

		write_node(leaf_table[in_array[i]]);
	}
	return(index + 1);

} /* compress */

/*
** Recursive portion of writetree().
*/
static void _writetree(NODE *node_ptr)
{
	BYTE i;

	if(node_ptr->child0 == NULL) {   /* leaf node */
		write_bit(0);
		for(i = 1;i != 0;i <<= 1) {
			write_bit((BYTE)(node_ptr->c & i));
		}
	}
	else {
		write_bit(1);
		_writetree(node_ptr->child0);
		_writetree(node_ptr->child1);
	}

} /* _writetree */

/*
** Writes a bit-coded huffman code tree to a buffer.
** Returns the length of output buffer in bytes.
*/
WORD writetree(NODE *root,BYTE *out_array)
{
	buffer = out_array;  /* set variables for write_bit() */
	index = 0;
	curr_bit = 1;

	_writetree(root);

	return(index + 1);

} /* writetree */

/*
** Combines two child nodes into a single branch node and
** returns a pointer to the branch.
** NULL indicates memory error.
*/
static NODE *build_branch(NODE *child0,NODE *child1)
{
	NODE *node_ptr;

	node_ptr = malloc(sizeof(NODE));
	if(node_ptr != NULL) {
		node_ptr->parent = NULL;
		node_ptr->freq = (child0->freq + child1->freq);
		node_ptr->child0 = child0;
		node_ptr->child1 = child1;
		child0->parent = node_ptr;
		child1->parent = node_ptr;
	}
	return(node_ptr);

} /* build_branch */

/*
** Constructs a code tree from node_list and returns the root node.
** NULL indicates memory.
*/
static NODE *build_tree(NODE **node_list,WORD num_nodes)
{
	WORD i,min1,min2,index1 = 0,index2 = 0;
	NODE *node_ptr = NULL;

	/* handle 1 or 0 nodes */
	if(num_nodes <= 1) {
		for(i = 0;i < TABLE_SIZE;i++) {
			if(node_list[i] != NULL)
				return(node_list[i]);   /* 1 node */
		}
		/* if 0 nodes, return dummy node */
		node_ptr = malloc(sizeof(NODE));
		memset(node_ptr,'\0',sizeof(NODE));
		return(node_ptr);
	}

	/* construct code tree */
	while(num_nodes > 1) {
		min1 = min2 = 0xFFFF;
		for(i = 0;i < TABLE_SIZE;i++) {
			if(node_list[i] == NULL)
				continue;   /* already taken */
			if(node_list[i]->freq < min1 || node_list[i]->freq < min2) {
				if(min1 < min2) {
					min2 = min1;
					index2 = index1;
				}
				min1 = node_list[i]->freq;
				index1 = i;
			}
		}
		node_ptr = build_branch(node_list[index1],node_list[index2]);
		if(node_ptr == NULL)
			return(NULL);
		node_list[index1] = node_ptr;
		node_list[index2] = NULL;
		num_nodes--;
	}

	/* return root node */
	return(node_ptr);

} /* build_tree */

/*
** Builds a code tree from the given file stream and returns a pointer
** to the root node. Returns NULL if no memory. NOTE: stream remains
** open when this function returns.
*/
NODE *gettree(FILE *stream)
{
	WORD i,num_nodes;
	WORD *freq_table;
	NODE **node_list,*root = NULL;

	/* construct frequency table */
	freq_table = malloc(TABLE_SIZE * sizeof(WORD));
	if(freq_table == NULL) {
		return(NULL);
	}
	memset(freq_table,'\0',TABLE_SIZE * sizeof(WORD));
	for(i = (WORD)fgetc(stream);!feof(stream);i = (WORD)fgetc(stream)) {
		freq_table[i]++;
	}

	node_list = malloc(TABLE_SIZE * sizeof(NODE *));
	if(node_list == NULL) {
		free(freq_table);
		return(NULL);
	}

	/* build a leaf node for each character */
	memset(leaf_table,'\0',sizeof(leaf_table));
	for(num_nodes = 0,i = 0;i < TABLE_SIZE;i++) {
		if(freq_table[i] != 0) {   /* if character is used */
			leaf_table[i] = malloc(sizeof(NODE));
			if(leaf_table[i] == NULL)
				break;;
			leaf_table[i]->c = (BYTE)i;
			leaf_table[i]->freq = freq_table[i];
			leaf_table[i]->child0 = NULL;
			leaf_table[i]->child1 = NULL;
			leaf_table[i]->parent = NULL;
			num_nodes++;
		}
		node_list[i] = leaf_table[i];
	}

	free(freq_table);

	/* construct code tree if no error */
	if(i == TABLE_SIZE)
		root = build_tree(node_list,num_nodes);

	/* free memory if error */
	if(root == NULL) {
		for(i = 0;i < TABLE_SIZE;i++) {
			if(leaf_table[i] != NULL) {
				free(leaf_table[i]);
			}
		}
	}
	free(node_list);
	return(root);

} /* gettree */
